

{\magonebf  6.5 Sets of parallel segments (segment\_set)}

An instance $S$ of the data type $segment\_set$ is a collection of items 
($seg\_item$). Every item in $S$ contains as key a line segment with a fixed 
direction $\alpha$ (see data type segment) and an information from a data 
type $I$, called the information type of $S$. $\alpha$ is called the
orientation of $S$. We use $<s,i>$ to denote the item with segment $s$ and 
information $i$. For each segment $s$ there is at most one item $<s,i> \in S$.


\bigskip
{\bf 1. Declaration of a segment set type}

\decl segment\_set I

introduces a new data type with name \name\ consisting of all 
segment sets  with information type $I$. 


\bigskip
{\bf 2. Creation of a segment set}


a) \create S (real\ \alpha)

b) \create S {}

creates an empty instance \var\ of type \name\ with orientation $\alpha$.
Variant b) creates a segment set of orientation zero, i.e., for horizontal 
segments.



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 3truecm & \hskip 5.5truecm &\cr
\+\op segment         key {seg\_item\ it} 
                                 {returns the segment of item $it$.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op I               inf {seg\_item\ it} 
                                 {returns the information of item $it$.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op seg\_item       insert {segment\ s,\ I\ i}
                                 {associates the information $i$ with segment}
\+\nop                           {$s$. If there is an item $<s,j>$ in \var }
\+\nop                           {then $j$ is replaced by $i$, else a new item }
\+\nop                           {$<s,i>$ is added to $S$. In both cases the}
\+\nop                           {item is returned.}
\smallskip
\+\op ps\_item        lookup {segment\ s} 
                                 {returns the item with segment $s$ (nil}
\+\nop                           {if no such item exists in \var).}
\smallskip
\+\op list(seg\_item) intersection {segment\ q}
                                 {returns all items $<s,i>\ \in\ S$ with}
\+\nop                           {$s \cap q \neq \emptyset$. \precond $q$ is}
\+\nop                           {orthogonal to the segments in \var.}
\smallskip
\+\op list(seg\_item) intersection {line\ l}
                                 {returns all items $<s,i>\ \in\ S$ with}
\+\nop                           {$s \cap l \neq \emptyset$. \precond $l$ is}
\+\nop                           {orthogonal to the segments in \var.}
\smallskip
\+\op void            del {segment\ s}         
                                 {deletes the item with segment $s$}
\+\nop                           {from \var.}
\smallskip
\+\op void            del\_item {seg\_item it}   
                                 {removes item $it$ from \var.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op void            change\_inf 
                                 {seg\_item\ it,\ I\ i}  {}
\+\nop                           {makes $i$ the information of item $it$.}
\+\nop                           {\precond $it$ is an item in \var.}
\smallskip
\+\op void            clear {}           
                                 {makes \var\ the empty segment\_set.}
\smallskip 
\+\op bool            empty {}           
                                 {returns true iff \var\ is empty.}
\smallskip 
\+\op int             size {}            
                                 {returns the size of \var.}



\bigskip
{\bf 4. Iteration}

{\bf forall\_seg\_items}($i,S$) 
$\{$ ``the items of $S$ are successively assigned to $i$ '' $\}$



\bigskip
{\bf 5. Implementation}

Segment sets are implemented by dynamic segment trees based on BB[$\alpha$]
trees. Operations key, inf, change\_inf, empty, and size take time $O(1)$, 
insert, lookup, del, and del\_item take time $O(\log^2 n)$ and an intersection
operation takes time $O(k + \log^2 n)$, where $k$ is the size of the returned
list. Here $n$ is the current size of the set. The space requirement is
$O(n\log n)$.
